package jianzhioffer;

/**
 * Author: Zhang Dongwei
 * Date: 2023/3/23 12:42
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 */
public class offer_51_数组中的逆序对 {

    public static void main(String[] args) {
        int[] nums = {7, 5, 6, 4};
        System.out.println(reversePairs(nums));
    }

//    暴力双重遍历，超时
    public static int reversePairs1(int[] nums) {
        int count = 0;
        for (int i=0; i<nums.length-1; i++){
            for (int j=i; j<nums.length;j++){
                if (nums[i]>nums[j])
                    count ++;
            }
        }
        return count;
    }

//    分治
    static int[] nums, tmp;
    public static int reversePairs(int[] nums) {
//        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }

    public static int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++];
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++];
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对
            }
        }
        return res;
    }
}
